package sort

type Radix struct {
	array  []int
	length int
	bucket [][]int
}

func (r *Radix) Init(array []int) {
	r.array = array
	r.getLen()
}

func (r *Radix) getLen() {
	size := len(r.array)
	top := r.array[0]
	for i := 1; i < size; i++ {
		if r.array[i] > top {
			top = r.array[i]
		}
	}
	r.length = 1
	top = top / 10
	for top > 0 {
		r.length++
		top = top / 10
	}
}

func (r *Radix) Sort(desc bool) {
	size := len(r.array)
	var i, j, k int
	m := 1
	for i = 1; i <= r.length; i++ { //循环次数为常数，即序列中最大数的位数
		r.bucket = make([][]int, 10)
		for j = 0; j < 10; j++ { //初始化0-9各位桶
			r.bucket[j] = make([]int, 0)
		}
		for j = 0; j < size; j++ { //遍历要排序的序列，将相应位数的元素加入到对应的位桶中
			k = r.array[j] / m % 10
			r.bucket[k] = append(r.bucket[k], r.array[j])
		}
		r.array = make([]int, 0) //清空原序列数组
		if desc {
			for j = 9; j >= 0; j-- { //将9-0各位桶的数重新组装放到原序列数组当中
				r.array = append(r.array, r.bucket[j]...)
			}
		} else {
			for j = 0; j < 10; j++ { //将9-0各位桶的数重新组装放到原序列数组当中
				r.array = append(r.array, r.bucket[j]...)
			}
		}
		m = m * 10
	}
}

func (r *Radix) Display() []int {
	return r.array
}
